Termination w.r.t. Q proof of /home/nowonder/forschung/aprove/satrung/aprove/lpar1/SK90SLASH4.52.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.

Q DP problem:
The TRS P consists of the following rules:

S₁(g₂(x, y)) -> S₁(y)
S₁(g₂(x, y)) -> S₁(x)
S₁(f₂(x, y)) -> S₁(x)
S₁(g₂(x, y)) -> G₂(s₁(x), s₁(y))
F₂(g₂(x, y), g₂(u, v)) -> G₂(f₂(x, u), f₂(y, v))
S₁(f₂(x, y)) -> F₂(s₁(y), s₁(x))
S₁(f₂(x, y)) -> S₁(y)
F₂(g₂(x, y), g₂(u, v)) -> F₂(y, v)
F₂(g₂(x, y), g₂(u, v)) -> F₂(x, u)

The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

S₁(g₂(x, y)) -> S₁(y)
S₁(g₂(x, y)) -> S₁(x)
S₁(f₂(x, y)) -> S₁(x)
S₁(g₂(x, y)) -> G₂(s₁(x), s₁(y))
F₂(g₂(x, y), g₂(u, v)) -> G₂(f₂(x, u), f₂(y, v))
S₁(f₂(x, y)) -> F₂(s₁(y), s₁(x))
S₁(f₂(x, y)) -> S₁(y)
F₂(g₂(x, y), g₂(u, v)) -> F₂(y, v)
F₂(g₂(x, y), g₂(u, v)) -> F₂(x, u)

The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph contains 2 SCCs with 3 less nodes.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPAfsSolverProof

          ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

F₂(g₂(x, y), g₂(u, v)) -> F₂(x, u)
F₂(g₂(x, y), g₂(u, v)) -> F₂(y, v)

The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using an argument filtering and a montonic ordering, at least one Dependency Pair of this SCC can be strictly oriented.

F₂(g₂(x, y), g₂(u, v)) -> F₂(x, u)
F₂(g₂(x, y), g₂(u, v)) -> F₂(y, v)

Used argument filtering: F₂(x1, x2) = x2
g₂(x1, x2) = g₂(x1, x2)
Used ordering: Precedence:

trivial

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPAfsSolverProof

              ↳ QDP

                ↳ PisEmptyProof

          ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPAfsSolverProof

Q DP problem:
The TRS P consists of the following rules:

S₁(g₂(x, y)) -> S₁(y)
S₁(g₂(x, y)) -> S₁(x)
S₁(f₂(x, y)) -> S₁(x)
S₁(f₂(x, y)) -> S₁(y)

The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using an argument filtering and a montonic ordering, at least one Dependency Pair of this SCC can be strictly oriented.

S₁(g₂(x, y)) -> S₁(y)
S₁(g₂(x, y)) -> S₁(x)
S₁(f₂(x, y)) -> S₁(x)
S₁(f₂(x, y)) -> S₁(y)

Used argument filtering: S₁(x1) = x1
g₂(x1, x2) = g₂(x1, x2)
f₂(x1, x2) = f₂(x1, x2)
Used ordering: Precedence:

trivial

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPAfsSolverProof

              ↳ QDP

                ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

s₁(a) -> a
s₁(s₁(x)) -> x
s₁(f₂(x, y)) -> f₂(s₁(y), s₁(x))
s₁(g₂(x, y)) -> g₂(s₁(x), s₁(y))
f₂(x, a) -> x
f₂(a, y) -> y
f₂(g₂(x, y), g₂(u, v)) -> g₂(f₂(x, u), f₂(y, v))
g₂(a, a) -> a

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.